#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int Item;
typedef struct node *link;

struct node {
    Item item;
    link next;
};

link reverse(link x);
void test_reverse_empty_list();
void test_reverse_single_node();
void test_reverse_two_nodes();
void test_reverse_three_nodes();
void test_original_head_next_is_null();

int main(int argc, char ** argv){
    printf("Testing reverse_empty_list...\n");
    test_reverse_empty_list();
    printf("Testing reverse_empty_list passed...\n");

    printf("Testing reverse_single_node...\n");
    test_reverse_single_node();
    printf("Testing reverse_single_node passed...\n");

    printf("Testing reverse_two_nodes...\n");
    test_reverse_two_nodes();
    printf("Testing reverse_two_nodes passed...\n");

    printf("Testing reverse_three_nodes...\n");
    test_reverse_three_nodes();
    printf("Testing reverse_three_nodes passed...\n");

    printf("Testing reverse_original_head_next_is_null...\n");
    test_original_head_next_is_null();
    printf("Testing reverse_original_head_next_is_null passed...\n");
    return 0;
}

/**
 * Program 3.10 List reversal
 * -----------------------------
 * This function reverses the links in a list, returning a pointer to the final node,
 * which then points to the next-to-final node, and so forth,
 * with the link in the first node of the original list set to NULL.
 * 
 * To accomplish this task, we need to maintain links to three consecutive nodes in the list.
 */
link reverse(link x){
    link r = NULL;
    link y = x;
    link t = x;
    
    while(y != NULL){
        t = y->next;

        y->next = r;

        r = y;
        y = t;
    }

    return r;
}

void test_reverse_empty_list() {
    link head = NULL;
    link result = reverse(head);
    assert(result == NULL);
}

void test_reverse_single_node() {
    link a = malloc(sizeof(struct node));
    a->next = NULL;
    link result = reverse(a);
    assert(result == a);
    assert(a->next == NULL); // 确保 next 未被修改
    free(a);
}

void test_reverse_two_nodes() {
    link a = malloc(sizeof(struct node));
    link b = malloc(sizeof(struct node));
    a->next = b;
    b->next = NULL;
    
    link result = reverse(a);
    
    assert(result == b);      // 新头节点是原尾节点 b
    assert(b->next == a);     // b 指向 a
    assert(a->next == NULL);  // a 是尾节点
    
    free(a);
    free(b);
}

void test_reverse_three_nodes() {
    link a = malloc(sizeof(struct node));
    link b = malloc(sizeof(struct node));
    link c = malloc(sizeof(struct node));
    a->next = b;
    b->next = c;
    c->next = NULL;
    
    link result = reverse(a);
    
    assert(result == c);      // 新头节点是 c
    assert(c->next == b);     // c → b
    assert(b->next == a);     // b → a
    assert(a->next == NULL);  // a 是尾节点
    
    free(a);
    free(b);
    free(c);
}

void test_original_head_next_is_null() {
    link a = malloc(sizeof(struct node));
    link b = malloc(sizeof(struct node));
    a->next = b;
    b->next = NULL;
    
    reverse(a);
    assert(a->next == NULL); // 原头节点 a 的 next 必须为 NULL
    
    free(a);
    free(b);
}
